

function GFGrammar(abstract, concretes) {
    this.abstract = abstract;
    this.concretes = concretes;
    for (var cnc in concretes)
	this.concretes[cnc].abstract = abstract;
}

function GFAbstract(startcat, types) {
    this.startcat = startcat;
    // this.types = {fname: new Type([cat, ...], cat), ...}
    this.types = types;
}

function GFConcrete(flags, productions, functions, sequences, categories, nr_cats) {
    this.abstract = undefined;
    // this.flags = {...}
    this.flags = flags;
    // this.productions = {cat: [new Apply(fun, [new PArg(cat), ...]), new Coerce(cat), ...], ...}
    this.productions = {};
    for (var i in productions) 
	this.productions[mkCat(i)] = productions[i];
    // this.functions = {fun: new CncFun(absfun, [seq,...]), ...}
    this.functions = {};
    for (var i = 0; i < functions.length; i++) 
	this.functions[mkFun(i)] = functions[i];
    // this sequences = {seq: [new SymLit(arg,param), new SymCat(arg,param), new SymKS("word"), ...], ...}
    this.sequences = {};
    for (var i = 0; i < sequences.length; i++) 
	this.sequences[mkSeq(i)] = sequences[i];
    // this.categories = {abscat: [cat,...], ...}
    // this.inversecats = {cat: abscat, ...}
    this.categories = {};
    this.inversecats = {};
    for (var abscat in categories) {
	this.categories[abscat] = [];
	for (var i = categories[abscat].s; i <= categories[abscat].e; i++) {
	    this.categories[abscat].push(mkCat(i));
	    this.inversecats[mkCat(i)] = abscat;
	}
    }
    // this.nr_cats = (integer)
    this.nr_cats = nr_cats;

    // this.coercions = {cat: [cat, ...], ...}
    // this.lincats = {cat: arity(integer)}
    // this.linfuns = {absfun: {[cat,...]: [{fun:fun, cat:cat, seqs:[seq,...]}, ...], ...} , ...}
    this.coercions = {};
    this.lincats = {};
    this.linfuns = {};
    for (var cat in this.productions) {
	setdefault(this.coercions, cat, []).push(cat);
	var prods = this.productions[cat];
	for (var i = 0; i < prods.length; i++) {
	    var prod = prods[i];
	    if (prod instanceof Coerce) {
		setdefault(this.coercions, prod.cat, []).push(cat);
	    } else {
		var cncfun = this.functions[prod.fun];
		var lf = setdefault(this.linfuns, cncfun.absfun, {});
		var children = [];
		for (var j = 0; j < prod.children.length; j++) 
		    children.push(prod.children[j].parg);
		setdefault(lf, children, []).push({fun:prod.fun, cat:cat, seqs:cncfun.seqs});
		var arity = cncfun.seqs.length;
		setdefault(this.lincats, cat, arity);
		if (this.lincats[cat] != arity) alert("Mismatching linfun arities for cat: " + cat);
	    }
	}
    }
}

/** GFConcrete.linearise(tree):
   @param tree: a GFTree instance
   @return: an Array of {word:String, node:String} Arrays
**/
GFConcrete.prototype.linearise = function (tree, node) {
    if (node == null) node = "";
    var results = _linearise(this, tree, node);
    return results[0].lin[0];
}

function _linearise(concrete, tree, node) {
    var results = [];
    var absfun = tree.node;
    var linfuns = concrete.linfuns[absfun];
    var all_dtrcatlins = tree.dtrs.map(function(dtr,k){
	return _linearise(concrete, dtr, node + k);
    });
    var all_dtrcatlins_product = productlist(all_dtrcatlins);
    foreach(all_dtrcatlins_product, function(dtrcatlins) {
	dtrcats = dtrcatlins.map(function(catlin){return catlin.cat});
	dtrlins = dtrcatlins.map(function(catlin){return catlin.lin});
	var coerced_dtrcats = dtrcats.map(function(cat){return concrete.coercions[cat]});
	var coerced_dtrcats_product = productlist(coerced_dtrcats);
	foreach(coerced_dtrcats_product, function(dtrcs) {
	    var fun_cat_seqs_list = linfuns[dtrcs];
	    foreach(fun_cat_seqs_list, function(fun_cat_seq) {
		var fun = fun_cat_seq.fun;
		var cat = fun_cat_seq.cat;
		var seqs = fun_cat_seq.seqs;
		var lin = [];
		foreach(seqs, function(seqnr) {
		    var seq = concrete.sequences[seqnr];
		    lin.push([]);
		    var phrase = lin[lin.length-1];
		    foreach(seq, function(arg) {
			if (arg instanceof SymCat) {
			    var dtrs = dtrlins[arg.arg][arg.param];
			    for (var p = 0; p < dtrs.length; p++) 
				phrase.push(dtrs[p]);
			} else if (arg instanceof SymKS) {
			    for (var p = 0; p < arg.tokens.length; p++) 
				phrase.push({word:arg.tokens[p], node:node});
			}
		    });
		});
		results.push({cat:cat, lin:lin});
	    });
	});
    });
    return results;
}


//////////////////////////////////////////////////////////////////////
// GF trees

// convenience factory function for creating GF trees
function T(node, type, dtrs) {
    return new GFTree(node, type, dtrs);
}

/** new GFTree(node, type, ?dtrs): constructor for creating GF trees
   @param node, type: String
   @param dtrs: an Array of GFTree's
   @return: a new GFTree object
**/
function GFTree(node, type, dtrs) {
    this.node = node;
    this.type = type;
    this.dtrs = dtrs || [];
}

/** GFTree.equals(other): checks if two trees are extensionally equal
    @param other: another GFTree
**/
GFTree.prototype.equals = function(other) {
    return other instanceof GFTree && 
	this.node == other.node && 
	this.type == other.type &&
	this.dtrs.length == other.dtrs.length &&
	this.dtrs.every(function(dtr,i){return dtr.equals(other.dtrs[i])});
}

/** GFTree.traverse(f): applies a function to all subtrees
   @param f: a function taking the node, the type and the whole subtree as argument
**/
GFTree.prototype.traverse = function(f) {
    f(this.node, this.type, this);
    foreach(this.dtrs, function(dtr) {
	dtr.traverse(f);
    });
}

/** GFTree.find(f): finds the first node for which the function returns true
   @param f: a function taking the whole subtree as argument
**/
GFTree.prototype.find = function(f) {
    return _GFTree_find(this, f);
}

function _GFTree_find(tree, f) {
    if (f(tree))
        return "";
    if (tree instanceof GFTree) {
        for (var i=0; i<tree.dtrs.length; i++) {
            // console.log(this, i, this.dtrs, this.dtrs[i]);
            var fnd = _GFTree_find(tree.dtrs[i], f);
            if (fnd != null) 
                return i + fnd;
        }
    }
}

/** GFTree.toString(?focusnode, ?prefix, ?suffix)
    @param focusnode: the highlighted node (a string of digits)
    @param prefix, suffix: the string that should be used for highlighting
    @return: a String
**/
GFTree.prototype.toString = function(focusnode, prefix, suffix) {
    if (prefix == null) prefix = "*";
    if (suffix == null) suffix = "";
    return _GFTree_toString(this, focusnode, prefix, suffix);
}

function _GFTree_toString(tree, focusnode, prefix, suffix) {
    var result;
    if (tree instanceof GFTree) {
        result = tree.node + ":" + (tree.type || "?");
        foreach(tree.dtrs, function(dtr, n) {
	    var newnode = focusnode && focusnode[0] == n && focusnode.slice(1);
	    result += " " + _GFTree_toString(dtr, newnode, prefix, suffix);
        });
    } else if (tree == null) {
        result = "?";
    } else {
        result = "" + tree;
    }
    if (focusnode === "") 
	return prefix + "(" + result + ")" + suffix;
    else
	return "(" + result + ")";
}

/** GFTree.copy()
    @return: a deep copy of the tree
**/
GFTree.prototype.copy = function() {
    return T(this.node, this.type,
	     this.dtrs.map(function(dtr){
		 return dtr.copy();
	     }));
}

/** GFTree.getSubtree(node)
    @param node: node reference (a string of digits)
    @return: the subtree specified by the given node
**/
GFTree.prototype.getSubtree = function(node) {
    var subtree = this;
    for ( var i = 0; i < node.length; i++) {
	var n = node[i];
        subtree = subtree.dtrs[n];
	if (!subtree) return;
    }
    return subtree;
};

/** GFTree.updateSubtree(node, update)
    @param node: node reference (a string of digits)
    @param update: a function that updates the specified subtree
    -- or a tree which should replace the existing subtree
**/
GFTree.prototype.updateSubtree = function(node, update) {
    var parent = this.getSubtree(node.slice(0, -1));
    var n = node[node.length-1];
    if (update instanceof GFTree) {
        parent.dtrs[n] = update;
    } else {
        parent.dtrs[n] = update(parent.dtrs[n]);
    }
}

/** GFTree.updateCopy(node, update)
    @param node: node reference (a string of digits)
    @param update: a function that updates the specified subtree
    -- or a tree which should replace the existing subtree
    @return: an updated copy of the tree - the original tree is left unchanged
**/
GFTree.prototype.updateCopy = function(node, update) {
    var newtree = this.copy();
    newtree.updateSubtree(node, update);
    return newtree;
}


function parseFocusedTree(descr) {
    var tokens = descr
        .replace(/(\*?)\( */g," $1(")
        .replace(/\)/g," ) ")
        .replace(/^ +| +$/g,"")
        .split(/ +/);
    var focus = null;
    var stack = [T()];
    tokens.forEach(function(token){
        if (token[0] == "*") {
            focus = stack.map(function(t){return t.dtrs.length}).join("").slice(1);
            token = token.slice(1);
        }
        if (token[0] == "(") {
            if (stack.length == 1 && stack[0].dtrs.length > 0) {
                console.log("PARSE ERROR: Expected end-of-string, found '(': " + descr);
            } else if (token.length <= 1) {
                console.log("PARSE ERROR: Expected node, found end-of-string: " + descr);
            } else {
                nodetype = token.slice(1).split(":");
                node = nodetype[0];
                type = nodetype[1] || null;
                stack.push(T(node, type));
            }
        } else if (token == ")") {
            if (stack.length == 1) {
                var err = (stack[0].dtrs.length == 0) ? "No matching open bracket" : "Expected end-of-string";
                console.log("PARSE ERROR: " + err + ", found ')': " + descr);
            } else {
                var tree = stack.pop();
                stack[stack.length-1].dtrs.push(tree);
            }
        } else {
            console.log("PARSE ERROR: Unknown token " + token + ": " + descr);
        }
    });
    if (stack.length > 1) {
        console.log("PARSE ERROR: Expected close bracket, found end-of-string: " + descr);
    } else if (stack[0].dtrs.length == 0) {
        console.log("PARSE ERROR: Expected open bracket, found end-of-string: " + descr);
    } else {
        return {tree:stack[0].dtrs[0], focus:focus};
    }
}


//////////////////////////////////////////////////////////////////////
// utility functions

/** productlist(pools): the cartesian product of an Array of Arrays
    @param pools: an Array of Arrays
    @return: the cartesian product as an Array of Arrays
**/
function productlist(pools) {
    var results = [[]];
    foreach(pools, function(pool) {
	var oldresults = results;
	results = [];
	foreach(oldresults, function(oldres) {
	    foreach(pool, function(k) {
		results.push(oldres.concat(k));
	    });
	});
    });
    return results;
}

/** setdefault(dict, key, defval): lookup key in dict, and set it to defval if not there
    @param dict: an Object
    @param key: the String key
    @param defval: the default value to set, if key doesn't have a value already
    @return: the result of looking uå key in dict
**/
function setdefault(dict, key, defval) {
    if (dict[key] == null) 
	dict[key] = defval;
    return dict[key];
}

/** foreach(sequence, fun): apply fun to each value in sequence
    @param sequence: a sequence - an Array or a String
    @param fun: a function on arguments of the sequence
**/
function foreach(sequence, fun) {
    if (sequence != null) {
	for (var i = 0; i < sequence.length; i++) {
	    fun(sequence[i], i, sequence);
	}
    }
}

/** startswith(string, prefix)
    @param string, prefix: Strings
    @return: True if string starts with prefix
**/
function startswith(str, prefix) {
    if (typeof str == "string" && typeof prefix == "string")
	return str.slice(0, prefix.length) == prefix;
}


//////////////////////////////////////////////////////////////////////
// functions for creating GF grammars from auto-generated javascript
// DO NOT RELY ON THESE - they might change whenever GF's output format changes

function mkFun(i) { return "F" + i }
function mkCat(i) { return "C" + i }
function mkSeq(i) { return "S" + i }

function Type(children, abscat) {
    this.children = children;
    this.abscat = abscat;
}

function Coerce(cat) {
    this.cat = mkCat(cat);
}

function PArg(cat) {
    this.parg = mkCat(cat);
}

function Apply(fun, children) {
    this.fun = mkFun(fun);
    this.children = children;
}

function CncFun(absfun, seqs) {
    this.absfun = absfun;
    this.seqs = [];
    for (var i = 0; i < seqs.length; i++)
	this.seqs.push(mkSeq(seqs[i]));
}

function SymLit(arg, param) {
    this.arg = arg; 
    this.param = param;
}

function SymCat(arg, param) {
    this.arg = arg;
    this.param = param;
}

function SymKS() {
    this.tokens = [];
    for (var i = 0; i < arguments.length; i++) {
	this.tokens.push(arguments[i]);
    }
}


//////////////////////////////////////////////////////////////////////
// pretty-printing
// DO NOT RELY ON THESE - they might change without warning

function linPrettyString(lin, focusnode, prefix, suffix) {
    if (!prefix) prefix = "*";
    if (!suffix) suffix = "";
    if (lin instanceof Array) {
	return lin.map(function(sublin){return linPrettyString(sublin, focusnode, prefix, suffix)}).join(" ");
    } else if (startswith(lin.node, focusnode)) {
	return prefix + lin.word + "/" + lin.node + suffix;
    } else {
	return lin.word + "/" + lin.node;
    }
}

function objectPrettyString(obj) {
    if (obj == null) {
	return "" + obj;
    } else if (obj instanceof Array) {
	var res = obj.map(function(o){
	    return objectPrettyString(o);
	});
	return "[" + res.join(", ") + "]";
    } else if (obj instanceof GFTree) {
	return "new GFTree(" + 
	    objectPrettyString(obj.node) + ", " + 
	    objectPrettyString(obj.type) + ", " + 
	    objectPrettyString(obj.dtrs) + ")";
    } else if (typeof obj == "object") {
	var res = [];
	for (var key in obj) {
	    res.push(key + ": " + objectPrettyString(obj[key]));
	}
	return "{" + res.join(", ") + "}";
    } else if (typeof obj == "string") {
	return '"' + obj + '"'
    } else {
	return "" + obj;
    }
}
